package leetcode

import kotlinetc.println

//https://leetcode.com/problems/combination-sum-ii/

/**
 * similar [combinationSum]
 * 和上一题 不同的是，每个数字不允许重复使用，只能用一次
 */
//TODO
fun main(args: Array<String>) {

    println("1 1 2 5 6 7")
    combinationSum2(intArrayOf(1, 2, 7, 6, 1, 7, 5), 8).println()
}

fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {

    val result = arrayListOf<List<Int>>()
    if (candidates.isEmpty()) return result
    //先排序，可以极大过滤掉不符合的情况
    candidates.sort()
    val used = Array<Boolean>(candidates.size, { false })
    combinationSum2Recursive(candidates, 0, 0, candidates[0], arrayListOf(), target, result)
    return result

}

/**
 *
 * 在 permutations 题目的基础上衍生而来[permute] [permuteUnique]
 * 由于不能重复使用数字，那么在排序后，直接按照数字的升序来去重，后面的数字必须比前面的大
 */
fun combinationSum2Recursive(candidates: IntArray, sum: Int, startIndex: Int,
                             last: Int, list: ArrayList<Int>, target: Int, result: ArrayList<List<Int>>) {
    for (i in startIndex until candidates.size) {
        if (candidates[i] < last) continue  //通过传排列中上一个数字，在下一层时候比较当前数字，强制只能往后寻找，这样去重
        if (i > 0 && candidates[i - 1] == candidates[i]) continue
        val r = candidates[i] + sum - target
        if (r == 0) {//不需要继续深度遍历，直接回到上一层
            list.add(candidates[i])
            result.add(ArrayList(list))
            list.removeAt(list.lastIndex)
            break
        } else if (r > 0) { //后续排列已经没有继续试探的必要
            break
        } else {
            list.add(candidates[i])
            combinationSum2Recursive(candidates, sum + candidates[i], startIndex + 1, candidates[i], list, target, result)
            list.removeAt(list.lastIndex)
        }
    }
}